翻訳と辞書 Words near each other ・ Split-finger ・ Split-finger fastball ・ Split-flap display ・ Split-fount Inking ・ Split-Hopkinson pressure bar ・ Split-horizon DNS ・ Split-intein circular ligation of peptides and proteins ・ Split-Karlovac Fault ・ Split-level hogfish ・ Split-level home ・ Split-octonion ・ Split-off point ・ Split-phase electric power ・ Split-pi topology ・ Split-quaternion ・ Split-radix FFT algorithm ・ Split-rail fence ・ Split-ring resonator ・ Split-single ・ Split-step method ・ Split-T ・ Split-ticket voting ・ Split/EP ・ Split/Second ・ Splitboard ・ Splitfin flashlightfish ・ SplitFire spark plug ・ Splithand Township, Itasca County, Minnesota ・ Splitlog Church ・ Splitrmx12 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Split-radix FFT algorithm ： ウィキペディア英語版 Split-radix FFT algorithm The split-radix FFT is a fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform (DFT), and was first described in an initially little-appreciated paper by R. Yavne (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, P. Duhamel and H. Hollmann.) In particular, split radix is a variant of the Cooley-Tukey FFT algorithm that uses a blend of radices 2 and 4: it recursively expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4. The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required real additions and multiplications) to compute a DFT of power-of-two sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 () ()), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a computer, the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.) The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired. ==Split-radix decomposition== Recall that the DFT is defined by the formula: :$X\_k\; =\; \backslash sum\_^\; x\_n\; \backslash omega\_N^$ where $k$ is an integer ranging from $0$ to $N-1$ and $\backslash omega\_N$ denotes the primitive root of unity: :$\backslash omega\_N\; =\; e^\},$ and thus :$\backslash omega\_N^N\; =\; 1$. The split-radix algorithm works by expressing this summation in terms of three smaller summations. (Here, we give the "decimation in time" version of the split-radix FFT; the dual decimation in frequency version is essentially just the reverse of these steps.) First, a summation over the even indices $x\_$. Second, a summation over the odd indices broken into two pieces: $x\_$ and $x\_$, according to whether the index is 1 or 3 modulo 4. Here, $n\_m$ denotes an index that runs from 0 to $N/m-1$. The resulting summations look like: :$X\_k\; =\; \backslash sum\_^\; x\_\; \backslash omega\_^$ + \omega_N^k \sum_^ x_ \omega_^ + \omega_N^ \sum_^ x_ \omega_^ where we have used the fact that $\backslash omega\_N^\; =\; \backslash omega\_^$. These three sums correspond to ''portions'' of radix-2 (size ''N''/2) and radix-4 (size ''N''/4) Cooley-Tukey steps, respectively. (The underlying idea is that the even-index subtransform of radix-2 has no multiplicative factor in front of it, so it should be left as-is, while the odd-index subtransform of radix-2 benefits by combining a second recursive subdivision.) These smaller summations are now exactly DFTs of length ''N''/2 and ''N''/4, which can be performed recursively and then recombined. More specifically, let $U\_k$ denote the result of the DFT of length ''N''/2 (for $k\; =\; 0,\backslash ldots,N/2-1$), and let $Z\_k$ and $Z\text{'}\_k$ denote the results of the DFTs of length ''N''/4 (for $k\; =\; 0,\backslash ldots,N/4-1$). Then the output $X\_k$ is simply: :$X\_k\; =\; U\_k\; +\; \backslash omega\_N^k\; Z\_k\; +\; \backslash omega\_N^\; Z\text{'}\_k.$ This, however, performs unnecessary calculations, since $k\; \backslash geq\; N/4$ turn out to share many calculations with . In particular, if we add ''N''/4 to ''k'', the size-''N''/4 DFTs are not changed (because they are periodic in ''k''), while the size-''N''/2 DFT is unchanged if we add ''N''/2 to ''k''. So, the only things that change are the $\backslash omega\_N^k$ and $\backslash omega\_N^$ terms, known as twiddle factors. Here, we use the identities: :$\backslash omega\_N^\; =\; -i\; \backslash omega\_N^k$ :$\backslash omega\_N^\; =\; i\; \backslash omega\_N^$ to finally arrive at: :$X\_k\; =\; U\_k\; +\; \backslash left(\; \backslash omega\_N^k\; Z\_k\; +\; \backslash omega\_N^\; Z\text{'}\_k\; \backslash right),$ :$X\_\; =\; U\_k\; -\; \backslash left(\; \backslash omega\_N^k\; Z\_k\; +\; \backslash omega\_N^\; Z\text{'}\_k\; \backslash right),$ :$X\_\; =\; U\_\; -\; i\; \backslash left(\; \backslash omega\_N^k\; Z\_k\; -\; \backslash omega\_N^\; Z\text{'}\_k\; \backslash right),$ :$X\_\; =\; U\_\; +\; i\; \backslash left(\; \backslash omega\_N^k\; Z\_k\; -\; \backslash omega\_N^\; Z\text{'}\_k\; \backslash right),$ which gives all of the outputs $X\_k$ if we let $k$ range from $0$ to $N/4-1$ in the above four expressions. Notice that these expressions are arranged so that we need to combine the various DFT outputs by pairs of additions and subtractions, which are known as butterflies. In order to obtain the minimal operation count for this algorithm, one needs to take into account special cases for $k\; =\; 0$ (where the twiddle factors are unity) and for $k\; =\; N/8$ (where the twiddle factors are $(1\; \backslash pm\; i)/\backslash sqrt$ and can be multiplied more quickly); see, e.g. Sorensen ''et al.'' (1986). Multiplications by $\backslash pm\; 1$ and $\backslash pm\; i$ are ordinarily counted as free (all negations can be absorbed by converting additions into subtractions or vice versa). This decomposition is performed recursively when ''N'' is a power of two. The base cases of the recursion are ''N''=1, where the DFT is just a copy $X\_0\; =\; x\_0$, and ''N''=2, where the DFT is an addition $X\_0\; =\; x\_0\; +\; x\_1$ and a subtraction $X\_1\; =\; x\_0\; -\; x\_1$. These considerations result in a count: $4\; N\; \backslash log\_2\; N\; -\; 6N\; +\; 8$ real additions and multiplications, for ''N''>1 a power of two. This count assumes that, for odd powers of 2, the leftover factor of 2 (after all the split-radix steps, which divide ''N'' by 4) is handled directly by the DFT definition (4 real additions and multiplications), or equivalently by a radix-2 Cooley–Tukey FFT step. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Split-radix FFT algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.